package cn.sjtu.data_structure.linked_list;

/**
 * @author syo 2319615164@qq.com
 * @description
 * @date 2024/5/12
 * @Copyright syo
 */
public class BiLinkedList <E>{
    public Node<E> head = null;
    public Node<E> tail = null;
    public int size = 0;
    public BiLinkedList(){}

    // 在开头插入元素
    public void addFirst(E e) {
        Node<E> newNode = new Node<E>(null, e, null);
        size++;
        if (head == null) {
            head = newNode;
            tail = newNode;
            return;
        }
        newNode.next = head;
        head.prev = newNode;
        head = newNode;
    }

    // 插入在尾部位置
    public void addLast(E e) {
        Node<E> newNode = new Node<E>(null, e, null);
        size++;

        if (tail == null) {
            head = newNode;
            tail = newNode;
            return;
        }

        newNode.prev = tail;
        tail.next = newNode;
        tail = newNode;
    }

    // 插入到第i个元素后位置
    public void insert(int index, E e) {
        if (index <= 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }

        Node<E> cur = head;
        for (int i = 1; i < index; i++) {
            cur = cur.next;
        }

        Node<E> newNode = new Node<E>(null, e, null);
        newNode.prev = cur;
        newNode.next = cur.next;
        if (cur.next != null) {
            cur.next.prev = newNode;
        }
        cur.next = newNode;
        size++;
    }

    // 删除头部元素
    public Node<E> removeFirst() {
        if (size <= 0) {
            throw new IndexOutOfBoundsException();
        }
        Node<E> result = head;
        if (size == 1) {
            head = null;
            tail = null;
            size--;
            return result;
        }

        head = head.next;
        head.prev = null;
        size--;
        return result;
    }

    // 删除尾部元素
    public Node<E> removeLast() {
        if (size <= 0) {
            throw new IndexOutOfBoundsException();
        }

        Node<E> result = tail;
        if (size == 1) {
            head = null;
            tail = null;
            size--;
            return result;
        }

        tail = tail.prev;
        tail.next = null;
        size--;
        return result;
    }

    public Node<E> remove(int index) {
        if (index <= 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }

        if (index == 1) {
            return removeFirst();
        }

        if (index == size) {
            return removeLast();
        }

        Node<E> cur = head;
        for (int i = 1; i < index; i++) {
            cur = cur.next;
        }
        cur.prev.next = cur.next;
        cur.next.prev = cur.prev;
        size--;
        return cur;
    }

    // 获取第i个元素的值
    public E get(int index) {
        if (index <= 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }


        Node<E> cur = head;
        for (int i = 1; i < index; i++) {
            cur = cur.next;
        }
        return cur.val;
    }

    // 修改第i个元素的值
    public void set(int index, E e) {
        if (index <= 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }


        Node<E> cur = head;
        for (int i = 1; i < index; i++) {
            cur = cur.next;
        }
        cur.val = e;
    }

    // 链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 链表中是否存在某个值
    public boolean contains(E e) {
        for (Node<E> cur = head; cur != null; cur = cur.next) {
            if (cur.val.equals(e)) {
                return true;
            }
        }
        return false;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (Node<E> cur = head; cur != null; cur = cur.next) {
            sb.append(cur.val);
            if (cur.next != null) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }

    public static void main(String[] args) {
        BiLinkedList<String> biLinkedList = new BiLinkedList<String>();
        biLinkedList.addFirst("b");
        biLinkedList.addLast("c");
        System.out.println(biLinkedList.toString());
    }
}
